{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #衣橱整理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wardrobeFinishing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #衣橱整理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>家居整理师将待整理衣橱划分为 <code>m x n</code> 的二维矩阵 <code>grid</code>，其中 <code>grid[i][j]</code> 代表一个需要整理的格子。整理师自 <code>grid[0][0]</code> 开始 <strong>逐行逐列</strong> 地整理每个格子。</p>\n",
    "\n",
    "<p>整理规则为：在整理过程中，可以选择&nbsp;<strong>向右移动一格&nbsp;</strong>或&nbsp;<strong>向下移动一格</strong>，但不能移动到衣柜之外。同时，不需要整理 <code>digit(i)&nbsp;+ digit(j)&nbsp;&gt; cnt</code> 的格子，其中 <code>digit(x)</code>&nbsp;表示数字&nbsp;<code>x</code> 的各数位之和。</p>\n",
    "\n",
    "<p>请返回整理师&nbsp;<strong>总共需要整理多少个格子</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 4, n = 7, cnt = 5\n",
    "<strong>输出：</strong>18\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n, m &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= cnt &lt;= 20</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ji-qi-ren-de-yun-dong-fan-wei-lcof](https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ji-qi-ren-de-yun-dong-fan-wei-lcof](https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n7\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        dirs = ((1, 0), (0, 1))\n",
    "        def get(x: int) -> int:\n",
    "            res = 0\n",
    "            while x:\n",
    "                res += x % 10\n",
    "                x //= 10\n",
    "            return res\n",
    "        q = deque([(0, 0)])\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        vis[0][0] = True\n",
    "        res = 1\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for a, b in dirs:\n",
    "                nx, ny = x + a, y + b\n",
    "                if nx >= m or ny >= n or vis[nx][ny] or get(nx) + get(ny) > cnt:\n",
    "                    continue\n",
    "                vis[nx][ny] = True\n",
    "                q.append((nx, ny))\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    direct = [[1, 0], [0, 1]]\n",
    "\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        digit = []\n",
    "        for x in range(max(m, n)):\n",
    "            ret = 0\n",
    "            while x > 0:\n",
    "                ret += (x % 10)\n",
    "                x = x // 10\n",
    "            digit.append(ret)\n",
    "\n",
    "        ans = 0\n",
    "        stack = [[0,0]]\n",
    "        visit = [[False] * n for _ in range(m)]\n",
    "        while len(stack) > 0:\n",
    "            loc = stack[-1]\n",
    "            del stack[-1]            \n",
    "            for i in range(0, 2):\n",
    "                x = loc[0] + self.direct[i][0]\n",
    "                y = loc[1] + self.direct[i][1]\n",
    "                if x < m and y < n and digit[x] + digit[y] <= cnt and not visit[x][y]:\n",
    "                    stack.append([x, y])\n",
    "                    visit[x][y] = True\n",
    "                    ans += 1\n",
    "        return ans + 1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        res = 0\n",
    "        vis = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        vis[0][0] = 1\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if self.digit(i) + self.digit(j) <= cnt:\n",
    "                    if i>0: vis[i][j] |= vis[i-1][j]\n",
    "                    if j>0: vis[i][j] |= vis[i][j-1]\n",
    "                res += vis[i][j]\n",
    "                    \n",
    "        return res   \n",
    "        \n",
    "    def digit(self, x):\n",
    "        res = 0\n",
    "        while x != 0:\n",
    "            res += x % 10\n",
    "            x = x // 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        self.m = m \n",
    "        self.n = n\n",
    "        self.cnt = cnt\n",
    "        matrix = [[0 for j in range(n)] for i in range(m)]\n",
    "        return self.dfs(0, 0, matrix)\n",
    "\n",
    "    def dfs(self, i, j, matrix):\n",
    "        if i < 0 or j < 0 or i >= self.m or j >= self.n or (self.get_digit_sum(i)+self.get_digit_sum(j)>self.cnt) or matrix[i][j]:\n",
    "            return 0\n",
    "        matrix[i][j] = 1\n",
    "        return 1 + self.dfs(i+1, j, matrix) + self.dfs(i, j+1, matrix)\n",
    "\n",
    "    def get_digit_sum(self, x):\n",
    "        total = 0\n",
    "        for ele in str(x):\n",
    "            total += int(ele)\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        def digit(i: int) -> int:\n",
    "            res = 0\n",
    "            while i > 0:\n",
    "                res = res + i % 10\n",
    "                i = i // 10\n",
    "            return res\n",
    "        def dfs(visit, i, j):\n",
    "            if i > m-1 or j > n-1 or visit[i][j] != 0 or digit(i) + digit(j) > cnt:\n",
    "                return False\n",
    "            visit[i][j] = 1\n",
    "            dfs(visit, i+1, j)\n",
    "            dfs(visit, i, j+1)\n",
    "        visit = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        dfs(visit, 0, 0)\n",
    "        return sum([sum(i) for i in visit])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        def digit(x):\n",
    "            ret=0\n",
    "            while x:\n",
    "                ret+=x%10\n",
    "                x//=10\n",
    "            return ret\n",
    "        \n",
    "        g=[[False]*n for _ in range(m)]\n",
    "        q=deque()\n",
    "        direct=[(1,0),(0,1)]\n",
    "        q.append((0,0))\n",
    "        g[0][0]=True\n",
    "        ans=1   # cnt>=0，必然有(0,0)作为答案\n",
    "        while q:\n",
    "            x,y=q.popleft()\n",
    "            for i in range(2):\n",
    "                nx=x+direct[i][0]\n",
    "                ny=y+direct[i][1]\n",
    "                if nx<0 or ny<0 or nx>=m or ny>=n or g[nx][ny] or digit(nx)+digit(ny)>cnt:\n",
    "                    continue\n",
    "                q.append((nx,ny))\n",
    "                g[nx][ny]=True\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "\n",
    "        def digit(k):\n",
    "            res = 0\n",
    "            while k > 0:\n",
    "                k, r = divmod(k, 10)\n",
    "                res += r\n",
    "            return res\n",
    "\n",
    "        res = 0\n",
    "        visited = [[False]*n for _ in range(m)]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            nonlocal res\n",
    "            # print(i, j, digit(i), digit(j))\n",
    "            visited[i][j] = True\n",
    "            if digit(i) + digit(j) <= cnt:\n",
    "                res += 1\n",
    "            else:\n",
    "                return\n",
    "            if i < m-1 and not visited[i+1][j]:\n",
    "                dfs(i+1,j)\n",
    "            if j < n-1 and not visited[i][j+1]:\n",
    "                dfs(i,j+1)\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        def neighhbor(i,j,m,n):\n",
    "            dir=[[0,1],[1,0]]\n",
    "            ans=[]\n",
    "            for e in dir:\n",
    "                ni,nj=i+e[0],j+e[1]\n",
    "                if ni>=0 and ni<m and nj>=0 and nj<n:\n",
    "                    ans.append([ni,nj])\n",
    "            return ans\n",
    "        def valid(i,j,k):\n",
    "            ans=0\n",
    "            while i>0:\n",
    "                ans+=i%10\n",
    "                i=i//10\n",
    "            while j>0:\n",
    "                ans+=j%10\n",
    "                j=j//10\n",
    "            return ans<=k\n",
    "\n",
    "\n",
    "        visited=[[0]*n for _ in range(m)]\n",
    "        self.s=0\n",
    "        def dfs(i,j,k,m,n):\n",
    "            if visited[i][j]:\n",
    "                return\n",
    "            visited[i][j]=1\n",
    "            if not valid(i,j,k):\n",
    "                return\n",
    "            self.s+=1\n",
    "            for e in neighhbor(i,j,m,n):\n",
    "                ni,nj=e[0],e[1]\n",
    "                dfs(ni,nj,k,m,n)\n",
    "            \n",
    "        \n",
    "        dfs(0,0,cnt,m,n)\n",
    "        return self.s "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        queue, visited = [(0, 0, 0, 0)], set()\n",
    "        while queue:\n",
    "            i, j, si, sj = queue.pop(0)\n",
    "            if i >= m or j >= n or cnt < si + sj or (i, j) in visited: continue\n",
    "            visited.add((i,j))\n",
    "            queue.append((i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj))\n",
    "            queue.append((i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8))\n",
    "        return len(visited)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        queue = deque([(0, 0)])\n",
    "        dirs = [(1, 0), (0, 1)]\n",
    "        visited = set([(0, 0)])\n",
    "        res = 0\n",
    "\n",
    "        # BFS\n",
    "        while queue:\n",
    "            l = len(queue)\n",
    "            # 遍历当前层\n",
    "            for _ in range(l):\n",
    "                posX, posY = queue.popleft()\n",
    "                # 将所有可行的下一步加入队列\n",
    "                for d in dirs:\n",
    "                    nextX, nextY = posX + d[0], posY + d[1]\n",
    "                    if nextX < m and nextY < n and digitSum(nextX) + digitSum(nextY) <= cnt:\n",
    "                        # 没有访问过\n",
    "                        if (nextX, nextY) not in visited:\n",
    "                            visited.add((nextX, nextY))  # 标记为已装入队列\n",
    "                            queue.append((nextX, nextY))\n",
    "            res += l\n",
    "\n",
    "        return res\n",
    "\n",
    "def digitSum(num):\n",
    "    res = 0\n",
    "    while num != 0:\n",
    "        res += num % 10\n",
    "        num //= 10\n",
    "    \n",
    "    return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        queue=collections.deque()\n",
    "        queue.append((0,0,0,0))\n",
    "        hset=set()\n",
    "        while queue:\n",
    "            i,j,si,sj=queue.popleft()\n",
    "            if i>=m or j>=n or si+sj>cnt or (i,j) in hset:\n",
    "                continue\n",
    "            hset.add((i,j))\n",
    "            queue.append((i+1,j,si-8 if (i+1)%10==0 else si+1,sj))\n",
    "            queue.append((i,j+1,si,sj-8 if (j+1)%10==0 else sj+1))\n",
    "        return len(hset)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def digitsum(n):\n",
    "    ans = 0\n",
    "    while n:\n",
    "        ans += n % 10\n",
    "        n //= 10\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        vis = set()\n",
    "        vis.add((0,0))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if ((i - 1, j) in vis or (i, j - 1) in vis) and digitsum(i) + digitsum(j) <= cnt:\n",
    "                    vis.add((i, j))\n",
    "        return len(vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def digit_sum(num):\n",
    "    return sum(map(int, str(num)))\n",
    "    \n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        def getDigitSum(x):\n",
    "            digit_sum = 0\n",
    "            while x > 0:\n",
    "                digit_sum += x % 10\n",
    "                x //= 10\n",
    "            return digit_sum\n",
    "\n",
    "        def isValidMove(i, j):\n",
    "            return i < m and j < n and getDigitSum(i) + getDigitSum(j) <= cnt\n",
    "\n",
    "        visited = set()\n",
    "        queue = deque([(0, 0)])\n",
    "\n",
    "        total_squares = 0\n",
    "\n",
    "        while queue:\n",
    "            i, j = queue.popleft()\n",
    "\n",
    "            if (i, j) in visited:\n",
    "                continue\n",
    "\n",
    "            visited.add((i, j))\n",
    "            total_squares += 1\n",
    "\n",
    "            # Move right\n",
    "            new_i, new_j = i, j + 1\n",
    "            if isValidMove(new_i, new_j):\n",
    "                queue.append((new_i, new_j))\n",
    "\n",
    "            # Move down\n",
    "            new_i, new_j = i + 1, j\n",
    "            if isValidMove(new_i, new_j):\n",
    "                queue.append((new_i, new_j))\n",
    "\n",
    "        return total_squares"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        def dfs(i, j, si, sj):\n",
    "            if i >= m or j >= n or cnt < si + sj or (i, j) in visited: return 0\n",
    "            visited.add((i,j))\n",
    "            return 1 + dfs(i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj) + dfs(i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8)\n",
    "\n",
    "        visited = set()\n",
    "        return dfs(0, 0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        visit = set()\n",
    "        def dfs(line, col, dig_l, dig_c):\n",
    "            if line >= m or col >= n or dig_l + dig_c > cnt or (line, col) in visit: return 0\n",
    "            visit.add((line, col))\n",
    "            return 1 + dfs(line + 1, col, dig_l + 1 if (line + 1) % 10 else dig_l - 8, dig_c) + dfs(line, col + 1, dig_l, dig_c + 1 if (col + 1) % 10 else dig_c - 8)\n",
    "        return dfs(0,0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, k: int) -> int:\n",
    "        def digitsum(n):\n",
    "            ans = 0\n",
    "            while n:\n",
    "                ans += n % 10\n",
    "                n //= 10\n",
    "            return ans\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if not 0 <= i < m or not 0 <= j < n or digitsum(i) + digitsum(j) > k:\n",
    "                return None\n",
    "            if (i, j) in visit:\n",
    "                return None\n",
    "            visit.add((i, j))\n",
    "            # dfs(i - 1, j)\n",
    "            dfs(i + 1, j)\n",
    "            # dfs(i, j - 1)\n",
    "            dfs(i, j + 1)\n",
    "\n",
    "        visit = set()\n",
    "        dfs(0, 0)\n",
    "        return len(visit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        def dfs(i,j,si,sj):\n",
    "            if i>=m or j>=n or cnt<si+sj or (i,j) in visited: return 0\n",
    "            visited.add((i,j))\n",
    "            return 1+dfs(i+1,j,si + 1 if (i + 1) % 10 else si - 8, sj)+dfs(i,j+1,si,sj+ 1 if (j+ 1)   % 10 else sj - 8)\n",
    "\n",
    "        visited=set()\n",
    "        return dfs(0, 0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m:int, n:int, cnt:int) -> int:\n",
    "        seen = set()\n",
    "        def dfs(i: int, j:int, si:int, sj:int) -> int:\n",
    "            if (i, j) in seen or i>=m or j>=n or si+sj>cnt:\n",
    "                return 0\n",
    "            seen.add((i, j))\n",
    "            if (i+1)%10:\n",
    "                down = dfs(i+1, j, si+1, sj)\n",
    "            else:\n",
    "                down = dfs(i+1, j, si-8, sj)\n",
    "            if (j+1)%10:\n",
    "                right = dfs(i, j+1, si ,sj+1)\n",
    "            else:\n",
    "                right = dfs(i, j+1, si ,sj-8)\n",
    "            \n",
    "            return 1 + right +down\n",
    "        self.pub = seen\n",
    "        return dfs(0, 0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        def digit(num):\n",
    "            _sum = 0\n",
    "            while num:\n",
    "                _sum += num % 10\n",
    "                num //= 10\n",
    "            return _sum\n",
    "        ret = 0\n",
    "        _set = list()\n",
    "        def recur(i, j):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n: return 0\n",
    "            if [i, j] in _set: return 0\n",
    "            if digit(i) + digit(j) > cnt: return 0\n",
    "            _set.append([i, j])\n",
    "            return recur(i + 1, j) + recur(i, j + 1) + 1\n",
    "        return recur(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        \n",
    "        def digit(x):\n",
    "            x = str(x)\n",
    "            sum_x = 0\n",
    "            for i in x:\n",
    "                sum_x = sum_x + int(i)\n",
    "            return sum_x\n",
    "\n",
    "        def count_x(i, j, cnt):\n",
    "            if i>=m or j>=n or (digit(i)+digit(j) > cnt) or ([i,j] in used):\n",
    "                return  0            \n",
    "            used.append([i,j])\n",
    "            counts = 1\n",
    "            counts = counts + count_x(i+1, j, cnt)\n",
    "            counts = counts + count_x(i, j+1, cnt)\n",
    "            return counts\n",
    "\n",
    "        if m * n == 0:\n",
    "            return 0\n",
    "        used = []\n",
    "        return count_x(0, 0,cnt)\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def getDigitSum(i, j):\n",
    "    ans = 0\n",
    "    while i:\n",
    "        ans += i % 10\n",
    "        i //= 10\n",
    "    while j:\n",
    "        ans += j % 10\n",
    "        j //= 10\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, k: int) -> int:\n",
    "        parents = list(range(m * n))\n",
    "\n",
    "        def find(x):\n",
    "            while x != parents[x]:\n",
    "                parents[x] = x = parents[parents[x]]\n",
    "            return x\n",
    "        \n",
    "        vals = [getDigitSum(i, j) <= k for i in range(m) for j in range(n)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if vals[idx := i * n + j]:\n",
    "                    r = find(idx)\n",
    "                    for x, y in ((i + 1, j), (i, j + 1)):\n",
    "                        if x < m and y < n and vals[code := n * x + y]:\n",
    "                            parents[find(code)] = r\n",
    "        r = find(0)\n",
    "        return sum(find(x) == r for x in range(len(parents)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        def search(i, j, visited):\n",
    "            if not 0 <= i < m or not 0 <= j < n or visited[i][j] or i // 10 + i % 10 + j // 10 + j % 10 > cnt: # 如果到达边界，或访问过，或每个数位之和大于k，则返回0\n",
    "                return 0\n",
    "            visited[i][j] = True # 标记为已访问\n",
    "            return search(i+1, j, visited) + search(i-1, j, visited) + search(i, j+1, visited) + search(i, j-1, visited) + 1 # 向后递归遍历\n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "        return search(0, 0, visited)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        def search(i, j, visited):\n",
    "            if not 0 <= i < m or not 0 <= j < n or visited[i][j] or i // 10 + i % 10 + j // 10 + j % 10 > cnt: # 如果到达边界，或访问过，或每个数位之和大于k，则返回0\n",
    "                return 0\n",
    "            visited[i][j] = True # 标记为已访问\n",
    "            return search(i+1, j, visited) + search(i-1, j, visited) + search(i, j+1, visited) + search(i, j-1, visited) + 1 # 向后递归遍历\n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "        return search(0, 0, visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "        def couts(x):\n",
    "            res = 0\n",
    "            while x:\n",
    "                res += x%10 \n",
    "                x //= 10\n",
    "            return res \n",
    "        count = 0\n",
    "        dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        # dir = [(0, 1), (1, 0)]\n",
    "        def backtrack(x, y):\n",
    "            nonlocal count  \n",
    "            if x<0 or y<0 or x>=m or y>=n or couts(x)+couts(y)>cnt or visited[x][y]: return 0\n",
    "            visited[x][y] = 1 \n",
    "            count = 1\n",
    "\n",
    "            for i, j in dir:\n",
    "                nx = x + i \n",
    "                ny = y + j \n",
    "                count += backtrack(nx, ny)\n",
    "                # visited[nx, ny] = 0\n",
    "\n",
    "            return count \n",
    "        return backtrack(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        def dfs(i,j,m,n,k,visited):\n",
    "            if i<0 or i>= m or j<0 or j>=n or (i//10+i%10+j//10+j%10)>k or visited[i][j]:\n",
    "                return 0\n",
    "            visited[i][j] = True\n",
    "            return dfs(i+1,j,m,n,k,visited) + dfs(i-1,j,m,n,k,visited) + dfs(i,j+1,m,n,k,visited) + dfs(i,j-1,m,n,k,visited) + 1\n",
    "        visited = [[False]*n for _ in range(m)]\n",
    "        return dfs(0,0,m,n,cnt,visited)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        # print('wardrobeFinishing')\n",
    "        def calculate(num: int):\n",
    "            ans = 0\n",
    "            while num >= 1:\n",
    "                ans += num % 10\n",
    "                num = num // 10\n",
    "            return ans\n",
    "\n",
    "        def check(i: int, j: int):\n",
    "            if i >= m or j >= n or  i < 0 or j < 0: return 0\n",
    "            if calculate(i) + calculate(j) > cnt or visited[i][j]:return 0\n",
    "            visited[i][j] = 1\n",
    "            return check(i + 1, j) + check(i - 1, j) + check(i, j - 1) + check(i, j + 1)\n",
    "\n",
    "        ans = 0\n",
    "        visited = []\n",
    "        for r in range(m):\n",
    "            visited.append([0 for c in range(n)])\n",
    "        check(0, 0)\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                ans += visited[r][c]\n",
    "                # if visited[r][c]:\n",
    "                    # print(r,c,end = ', ')\n",
    "                    # if ans % 8 == 0:\n",
    "                    #     print('\\n')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        def sum_of_digits(num1, num2):\n",
    "            res1 = sum([int(s) for s in str(num1)])\n",
    "            res2 = sum([int(s) for s in str(num2)])\n",
    "            return res1+res2\n",
    "        \n",
    "        def dfs(i, j, visited):\n",
    "            if 0<=i<m and 0<=j<n and visited[i][j]==False and (sum_of_digits(i,j)<= cnt):\n",
    "                visited[i][j] = True\n",
    "                return 1+ dfs(i+1,j,visited)+ dfs(i-1,j,visited)+ dfs(i,j+1,visited)+ dfs(i,j-1,visited)\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "            # if not (0<=i<m) or not (0<=j<n) or (sum_of_digits(i)+sum_of_digits(j) >k) or visited[i][j]:\n",
    "            #     return 0\n",
    "            # visited[i][j] = True\n",
    "            # return 1+dfs(i+1,j,visited) + dfs(i-1,j, visited) + dfs(i, j-1,visited) + dfs(i,j+1,visited)\n",
    "\n",
    "\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        return dfs(0, 0, visited)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        def digitSum(x):\n",
    "            ans = 0\n",
    "            while x:\n",
    "                ans += x % 10\n",
    "                x //= 10\n",
    "            return ans\n",
    "        def dfs(i, j, visited):\n",
    "            if not (0 <= i < m) or not(0 <= j < n) or (i,j) in visited or digitSum(i) + digitSum(j) > cnt:\n",
    "                return 0\n",
    "            visited.add((i, j))\n",
    "            return 1 + dfs(i+1, j, visited) + dfs(i-1, j, visited) + dfs(i, j+1, visited) + dfs(i, j-1, visited)\n",
    "        return dfs(0, 0, set())\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        \n",
    "        self.result = 0\n",
    "        grid = [[0] * n for _ in range(m)]\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0 or i > m-1 or j > n-1 or not check(i, j) or grid[i][j]:\n",
    "                return\n",
    "            \n",
    "            self.result += 1\n",
    "            grid[i][j] = 1\n",
    "            dfs(i-1, j)\n",
    "            dfs(i+1, j)\n",
    "            dfs(i, j-1)\n",
    "            dfs(i, j+1)\n",
    "        \n",
    "\n",
    "        def check(i, j):\n",
    "            sum_data = i // 10  + i % 10 + j // 10 + j % 10\n",
    "            if sum_data > cnt:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        result = [[False] * n for _ in range(m)]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if sum([int(value) for value in (str(i) + str(j))]) > cnt:\n",
    "                result[i][j] = False\n",
    "                return\n",
    "            else:\n",
    "                result[i][j] = True\n",
    "            for x, y in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\n",
    "                if 0 <= i + x < m and 0 <= j + y < n and not result[i + x][j + y]:\n",
    "                    dfs(i + x, j + y)\n",
    "\n",
    "        dfs(0, 0)\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if result[i][j]:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int):\n",
    "        def is_valid(i, j):\n",
    "            index_li = list(str(i) + str(j))\n",
    "            return sum([int(x) for x in index_li]) <= cnt\n",
    "        res = []\n",
    "        visited = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        def dfs(i, j, visited):\n",
    "            if not 0 <= i < m or not 0 <= j < n or visited[i][j] or not is_valid(i, j):\n",
    "                return\n",
    "            res.append((i, j))\n",
    "            visited[i][j] = 1\n",
    "            dfs(i-1, j, visited)\n",
    "            dfs(i+1, j, visited)\n",
    "            dfs(i, j-1, visited)\n",
    "            dfs(i, j+1, visited)\n",
    "            return\n",
    "\n",
    "        dfs(0, 0, visited)\n",
    "        return len(set(res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, k: int) -> int:\n",
    "        def digitsum(n):\n",
    "            ans = 0\n",
    "            while n:\n",
    "                ans += n % 10\n",
    "                n //= 10\n",
    "            return ans\n",
    "        def dfs(i,j):\n",
    "            if not 0<=i<m or not 0<=j<n or digitsum(i)+digitsum(j)>k:\n",
    "                return None\n",
    "            if (i,j) in visit:\n",
    "                return None\n",
    "            visit.add((i,j))\n",
    "            dfs(i-1,j)\n",
    "            dfs(i+1,j)\n",
    "            dfs(i,j-1)\n",
    "            dfs(i,j+1)\n",
    "        visit = set()\n",
    "        dfs(0,0)\n",
    "        return len(visit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, k: int) -> int:\n",
    "        def digitsum(n):\n",
    "            ans = 0\n",
    "            while n:\n",
    "                ans += n % 10\n",
    "                n //= 10\n",
    "            return ans\n",
    "        def dfs(i,j):\n",
    "            if not 0<=i<m or not 0<=j<n or digitsum(i)+digitsum(j)>k:\n",
    "                return None\n",
    "            if (i,j) in visit:\n",
    "                return None\n",
    "            visit.add((i,j))\n",
    "            dfs(i-1,j)\n",
    "            dfs(i+1,j)\n",
    "            dfs(i,j-1)\n",
    "            dfs(i,j+1)\n",
    "        visit = set()\n",
    "        dfs(0,0)\n",
    "        return len(visit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, k: int) -> int:\n",
    "        def num_sum(num):\n",
    "            ans = 0\n",
    "            quotient = num\n",
    "            while quotient:\n",
    "                quotient, remainder = divmod(quotient, 10)\n",
    "                ans += remainder\n",
    "            return ans\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if num_sum(i) + num_sum(j) > k:\n",
    "                return\n",
    "            visited.add((i, j))\n",
    "            for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:\n",
    "                if 0 <= x < m and 0 <= y < n and (x, y) not in visited:\n",
    "                    dfs(x, y)\n",
    "\n",
    "        visited = set()\n",
    "        dfs(0, 0)\n",
    "        return len(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:\n",
    "        def dfs(i: int, j: int, visited: List[List[bool]]):\n",
    "            nonlocal res\n",
    "            if i < 0 or j < 0 or i >= m or j >= n:\n",
    "                # 超出索引边界\n",
    "                return\n",
    "\n",
    "            if i // 10 + i % 10 + j // 10 + j % 10 > cnt:\n",
    "                # 坐标和超出 k 的限制\n",
    "                return\n",
    "\n",
    "            if visited[i][j]:\n",
    "                # 之前已经访问过当前坐标\n",
    "                return\n",
    "\n",
    "            # 走到一个合法坐标\n",
    "            res += 1\n",
    "            visited[i][j] = True\n",
    "\n",
    "            # DFS 遍历上下左右\n",
    "            dfs(i + 1, j, visited)\n",
    "            dfs(i, j + 1, visited)\n",
    "            dfs(i - 1, j, visited)\n",
    "            dfs(i, j - 1, visited)\n",
    "\n",
    "        # 记录合法坐标数\n",
    "        res = 0\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        dfs(0, 0, visited)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
